package main

import (
	"fmt"
)

func maopao(arr []int) []int {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}

	fmt.Println(arr)
	return arr
}
func erfen(arr []int, find int) int {
	result := -1
	left, right := 0, len(arr)-1
	for left <= right {
		mid := (left + right) / 2
		if find < arr[mid] {
			right = mid - 1
		} else if find > arr[mid] {
			left = mid + 1
		} else {
			result = mid
			return result
		}
	}
	return result

}
func main() {
	l := NewNodeList()
	l.InsertTail(1)
	l.InsertTail(2)
	l.InsertTail(3)
	//l.InsertHead(0)
	l.InsertPos(2, "xx")
	l.Print()
}

// 单向列表

type NodeList struct {
	root *Node
}
type Node struct {
	Data any
	Next *Node
}

func NewNodeList() *NodeList {
	return &NodeList{}
}

func (l *NodeList) InsertPos(pos int, data any) {
	if pos < 0 {
		l.InsertHead(data)
	} else if pos > l.NodeNum() {
		l.InsertTail(data)
	} else {
		node := l.root
		count := 0
		for node.Next != nil && count < pos {
			count++
			node = node.Next
		}
		insertNode := Node{Data: data}

		insertNode.Next = node.Next
		node.Next = &insertNode
	}

}
func (l *NodeList) DeleteNode(pos int) {

}
func (l *NodeList) NodeNum() int {

	if l.root == nil {
		return 0
	}
	num := 1
	node := l.root
	for node.Next != nil {
		num += 1
		node = node.Next
	}
	return num
}
func (l *NodeList) InsertHead(data any) {
	if l.root == nil {
		l.root = &Node{Data: data}
	} else {
		node := Node{
			Data: data,
		}
		node.Next = l.root
		l.root = &node
	}
}
func (l *NodeList) InsertTail(data any) {
	if l.root == nil {
		l.root = &Node{Data: data}
	} else {
		n := l.root
		for n.Next != nil {
			n = n.Next
		}
		n.Next = &Node{Data: data}
	}
}
func (l *NodeList) Print() {

	if l.root == nil {
		return
	}
	node := l.root
	fmt.Println(node.Data)
	for node.Next != nil {

		node = node.Next
		fmt.Println(node.Data)
	}
}
